package BZimmerman.AndroidWars;
import java.util.ArrayList;
import android.graphics.PointF;


	//This class was made as a more elegant solution to the original shortest path algo
	public class shortestPath {
		ArrayList<PointF> _path = new ArrayList<PointF>();
		int[][] masterMap, movementMap;
		int tiles, movementSquares;
		PointF start,end;
		shortestPath(int[][] levelMap, PointF start, PointF end, int tiles, int movementSquares){
			//System.out.println("Shortest Path");
			this.movementSquares = movementSquares;
			masterMap = new int[tiles][tiles];
			movementMap = new int[tiles][tiles];
			for(int y = 0; y < tiles; y++){
				for(int x = 0; x<tiles;x++){
					//Avoid walls
					if (levelMap[x][y]==0 && !(end.x==x && end.y==y)){
						masterMap[x][y] = -1;
					}else if((start.x==x && start.y==y)){
						masterMap[x][y] = 1;
					}else{
						masterMap[x][y] = 0;
					}
					movementMap[x][y] = levelMap[x][y];
				}
			}
			this.tiles = tiles;
			this.start = start;
			this.end = end;
		}
		public boolean returnUncounted(){
			for(int y = 0; y<tiles;y++){
				for(int x = 0; x< tiles;x++){
					if(masterMap[(int) end.x][(int) end.y] == 0){
						return true;
					}
				}
			}
			return false;
		}
		
		public ArrayList<PointF> returnPath(){
			//This map solver uses the water algorithm, which has far better time than the best-first I had in place previously
			ArrayList<PointF> _steps = new ArrayList<PointF>();
			int count = 1, increment = 0;
			boolean didSomething;
			while(returnUncounted()){
				didSomething = false;
				//System.out.println("Building Loop");
				for(int y = 0; y< tiles; y++){
					for(int x = 0; x<tiles;x++){
						if(masterMap[x][y] == count){
							if(x != 0){
								if(masterMap[x-1][y] == 0){
									masterMap[x-1][y] += (count+movementMap[x-1][y]);
									didSomething = true;
								}
							}
							if (y != 0){
								if(masterMap[x][y-1] == 0){
									masterMap[x][y-1] += (count+movementMap[x][y-1]);
									didSomething = true;
								}
							}
							if (x != tiles-1){
								if(masterMap[x+1][y] == 0){
									masterMap[x+1][y] += (count+movementMap[x+1][y]);
									didSomething = true;
								}
							}
							if (y != tiles-1){
								if(masterMap[x][y+1] == 0){
									masterMap[x][y+1] += (count+movementMap[x][y+1]);
									didSomething = true;
								}
							}
						}
					}
				}
				if(!didSomething && increment == movementSquares){
					_steps.add(start);
					return _steps;
				}else if (!didSomething){
					increment++;
				}else{
					increment = 0;
				}
				count++;
			}
			int build = masterMap[(int) end.x][(int) end.y];
			boolean stepFound = false;
			PointF current = new PointF(end.x,end.y);
			_steps.add(0, current);
			while(build>1){
				//System.out.println("Backtracking...");
				//System.out.println("Build: " + build);
				//System.out.println(current.x + " " + current.y);
				if(current.x != 0 && !stepFound){
					if(masterMap[(int) (current.x-1)][(int) current.y] == build-1){
						current = new PointF(current.x-1,current.y);
						stepFound = true;
					}
				}
				if (current.y != 0 && !stepFound){
					if(masterMap[(int) current.x][(int) (current.y-1)] == build-1){
						current = new PointF(current.x,current.y-1);
						stepFound = true;
					}
				}
				if (current.x != tiles-1 && !stepFound){
					if(masterMap[(int) (current.x+1)][(int) current.y] == build-1){
						current = new PointF(current.x+1,current.y);
						stepFound = true;
					}
				}
				if (current.y != tiles-1 && !stepFound){
					if(masterMap[(int) current.x][(int) (current.y+1)] == build-1){
						current = new PointF(current.x,current.y+1);
						stepFound = true;
					}
				}
				if(stepFound){
					stepFound = false;
					_steps.add(0, current);
				}
				build--;
			}
			//System.out.println("Steps: " + _steps.size());
			return _steps;
		}
	}

